/**
 * describe:
 *
 * @author chaP
 * @date 2019/01/10
 */
package CodingTest;

/**
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。

 本题中，一棵高度平衡二叉树定义为：

 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

 解题思路：用递归Recursion，首先构建一个新的函数求树的最大深度，
 然后求左子树最大深度，右子树最大深度，两者之差大于1就return false，然后菜判断左右子树是不是分别依旧是高度平衡树，结束。
 */
public class isBalanced {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){val = x;}
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int left = deepestHeight(root.left);
        int right = deepestHeight(root.right);
        if(Math.abs(left - right) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int deepestHeight(TreeNode node){
        if(node == null) return 0;
        int ld = deepestHeight(node.left);
        int rd = deepestHeight(node.right);
        return ld>rd?ld +1:rd+1;
    }
}
